#include"Heap.h"

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HeapInit(HP* php)
{
    assert(php);

    php->a = NULL;
    php->size = php->capacity = 0;
};

void HeapDestroy(HP* php)
{
    assert(php);

    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
};

void Swap(HPDataType* a, HPDataType* b)
{
    HPDataType tmp = *a;
    *a = *b;
    *b = tmp;
}

void AdjustUp(HPDataType* a, int child) //child是指定节点位置的下标 向上调整的前提是前面是堆
{
    int parent = (child - 1) / 2;      //二叉树中都像这样用child找parent
    while(child > 0)
    {
        if(a[child] < a[parent])
        {
            swap(&a[child],&a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

void HeapPush(HP* php, HPDataType x)   //添加元素
{
    assert(php);
    if(php->size == php->capacity)
    {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a,newcapacity * sizeof(HPDataType));
        if(tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }

        php->a = tmp;
        php->capacity = newcapacity;
    }

    php->a[php->size] = x;
    php->size++;

    AdjustUp(php->a, php->size - 1);
};

void AdjustDown(int* a, int size, int parent)      //向下调整的前提是两个子树是堆
{
    int child = parent * 2 + 1;

    while(child < size)
    {
        //假设左孩子小，如果错了则更新

        if(child + 1 < size && a[child + 1] < a[child])
        {
            child++;
        }

        if(a[child] < a[parent])
        {
            Swap(&a[child],&a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else{
            break;
        }
    }
}

// 规定删除堆顶 把首尾元素交换，再删除原首元素最后排序建成新堆
void HeapPop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    Swap(&php->a[0],&php->a[php->size - 1]);
    php->size --;    
    
    AdjustDown(php->a,php->size,0);                              //swap之后要重新排序
};

HPDataType HeapTop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    return php->a[0];
};
size_t HeapSize(HP* php)
{
    assert(php);

    return php->size;
};

bool HeapEmpty(HP* php)
{
    assert(php);

    return php->size == 0;
};

void HeapCreat(HP* php,HPDataType* a,int n)
{
    assert(php);
    php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
    if(php->a == NULL)
    {
        perror("malloc fail!");
        exit(-1);
    }
    memcpy(php->a,a,sizeof(HPDataType) * n);
    php->size = php->capacity = n;

    for(int i = (n - 1 - 1) / 2; i >= 0;i--)   //int i = (n - 1 - 1) / 2是最后一个非叶子节点的下标
    {
        AdjustDown(php->a, n, i);
    }
}
void HeapPrint(HP* php)
{
    assert(php);
    for(int i = 0;i < php->size;i++)
    {
        print("%d ",php->a[i]);
    }
    print("\n");
};


